package leetcode_900;

import java.util.Arrays;

/**
 *@author 周杨
 *CarFleet_853 一个车队 给定初始位置和速度 如果后面的赶上前面了 那么降速成为一个车队 问最终有多少车队到达目的地
 *describe:排序初始车的位置 按到达目的地的时间排序 AC 38%
 *2018年11月4日 下午2:00:17
 */
public class CarFleet_853 {
	class Car{
		int pos;
		double time;
		public Car(int pos,double time) {
			this.pos=pos;
			this.time=time;
		}
	}
	public int carFleet(int target, int[] position, int[] speed) {
		if(position.length==0)
			return 0;
		Car []cars=new Car[position.length];
        for(int i=0;i<position.length;++i) {
        	cars[i]=new Car(position[i],(double)(target-position[i])/speed[i]);//注意类型转换
        }
        Arrays.sort(cars,(o1,o2)->o1.pos-o2.pos);//按初始位置排序
        int res=0;
        for(int i=cars.length-1;i>0;--i) {//因为Car是按出发位置排序的 
        	if(cars[i].time<cars[i-1].time) ++res;//如果前面的比后面的早到 那后面的永远赶不上了
        	else cars[i-1]=cars[i];//否则赶上了 降速
        }
        return res+1;
    }
}
